package com.hexb.arithmetic.astart
{
	import com.hexb.Utils;
	
	public class AStartArithmetic
	{
		private const BARRIER:int = 7 ;//障碍物标记--大于7的均为障碍物
		private const CLOSE:int = 2 ;//关闭列表标记
		private const OPEN:int = 3 ;//开启列表标记
		
		private var tn1:int = 0 ;
		private var tn2:int = 0 ;
		private var tn3:int = 0 ;
		
		public function AStartArithmetic()
		{
		}
		/**
		 * @parameter grid 二维数组，位置上1表示有障碍物，0表示该位置畅通 
		 * @parameter startPoint 起始点
		 * @parameter endPoint 终点
		 * @return 从起点到终点的最短路径
		 * */
		public function getAtoBPath(grid:Array,startPoint:APoint,endPoint:APoint,canAcross:Boolean=true):Array{
			var t:uint = new Date().time;
			var lastPoint:APoint = searchPath(grid,startPoint,endPoint,canAcross);
			var t1:uint = new Date().time ;
			trace("总耗费：(ms)" + (t1-t));
			trace("求开启列表中最小F值耗费：(ms)" + tn1);
			trace("检查某点是否在列表开启列表中耗费：(ms)" + tn2);
			var temp:APoint ;
			var path:Array = new Array();
			temp = lastPoint ;
			while(temp!=null){
				path.push(temp);
				temp = temp.parentPoint ;
			}
			var resultPath:Array = path.reverse();
			resultPath.splice(0,1);
			return resultPath;
		}
		
		/*
		* @parameter grid 二维数组，位置上1表示有障碍物，0表示该位置畅通 
		* @parameter startPoint 起始点
		* @parameter endPoint 终点
		* @return 从起点到终点的最短路径
		* */
		public function searchPath(grid:Array,startPoint:APoint,endPoint:APoint,canAcross:Boolean=true):APoint{
			
			//开启列表
			var openList:Array = null;
			openList = new Array();
			//将起点加入到开启列表中
			openList.push(startPoint);
			var foundPoint:APoint = searchPathWithList(grid,endPoint,openList,canAcross) ;
			//如果开启列表为空，则表示不能到达
			while(foundPoint==null && openList.length>0){
				foundPoint = searchPathWithList(grid,endPoint,openList,canAcross) ;
			}
			return foundPoint ;
		}
		
		//寻找路径
		private function searchPathWithList(grid:Array,endPoint:APoint,
											openList:Array,
											canAcross:Boolean):APoint{
			//检查终点目标是否在关闭列表中
			var temp:APoint = null;
			if(grid[endPoint.y][endPoint.x]==CLOSE){
				return endPoint ;
			}
			//从开启列表中查找F值最小的点
			temp = findMinFPoint(openList);
			//改添加到关闭列表为在场地上标记，可很大程度上提高性能
			grid[temp.y][temp.x] = CLOSE ;
			//查找周边点，并计算G，H，F值
			searchAreaPoint(grid,temp,endPoint,openList,canAcross);
			return null;
		}
		
		
		private function sortFun(a:APoint,b:APoint):int{
			if(a.fValue < b.fValue){
				return -1 ;
			}
			if(a.fValue > b.fValue){
				return 1 ;
			}
			return 0 ;
		}
		
		
		/*查找列表中H值最小的点
		*同时删队该点
		*/
		private function findMinFPoint(list:Array):APoint{
			var t:uint = new Date().time;
			var min:APoint = null ;
			list.sortOn("fValue",Array.NUMERIC);
			min = list.shift() as APoint ;
			var t1:uint = new Date().time ;
			tn1 += (t1-t);
			return min ;
		}
		
		/*
		*查找当前点周围的可开启点列表,同时并计算G，H值	
		*@parameter currentPoint 当前点
		*@parameter startPoint 寻路的起点
		*@parameter endPoint 寻路的到达点终点
		*@parameter openList
		*@parameter closeList
		*@parameter canAcross 是否能穿转角
		**/
		private function searchAreaPoint(grid:Array,
										 currentPoint:APoint,
										 endPoint:APoint,
										 openList:Array,
										 canAcross:Boolean):void{
			var sx:int = currentPoint.x - 1 > -1 ? currentPoint.x - 1 : currentPoint.x ;
			var sy:int = currentPoint.y - 1 > -1 ? currentPoint.y - 1 : currentPoint.y ;
			var ex:int = currentPoint.x + 1 < getMaxCol(grid) ? currentPoint.x + 1 : currentPoint.x ;
			var ey:int = currentPoint.y + 1 < grid.length ? currentPoint.y + 1 : currentPoint.y ;
			
//			var sx:int = Math.max(0,currentPoint.x - 1);
//			var sy:int = Math.max(0,currentPoint.y - 1);
//			var ex:int = Math.min(getMaxCol(grid)-1,currentPoint.x+1) ;
//			var ey:int = Math.min(grid.length-1,currentPoint.y + 1);
			
			var openPoint:APoint = null ;
			
			var x:int ;
			var y:int ;
			for(x = sx ;x<=ex ;x++){
				for(y=sy ;y<=ey ;y++){
					//如果当前位置为寻路的终点
					if(x==endPoint.x && y==endPoint.y){
						endPoint.parentPoint = currentPoint ;
						//终点添加进关闭列表
						grid[y][x] = CLOSE ;
						return ;
					}
					
					//如果是当前点位置，舍弃
					if(x==currentPoint.x && y==currentPoint.y){
						continue ;
					}
					//如果当前点位置为障碍物，舍弃
					if(grid[y][x]>=BARRIER){
						continue ;
					}
					
					/**可选项，是否可以穿过转角，即当前位置与对角位置之间有障碍物时*/
					if(canAcross==false){//如果不能穿过转角障碍物
						//如果此位置与目标位置处于对角关系
						if(Math.abs(x-currentPoint.x) + Math.abs(y-currentPoint.y)==2){
							//判断此位置与目标位置转角处是否有障碍物
							if(grid[y][currentPoint.x]>=BARRIER){
								continue ;
							}
							if(grid[currentPoint.y][x]>=BARRIER){
								continue ;
							}
						}
					}
					
					//如果当前点在关闭列表中，舍弃
					if(grid[y][x]==CLOSE){
						continue ;
					}
					
					var temp:APoint = new APoint(x,y);
					//如果在开启列表中
					openPoint = checkPointInList(temp,grid) ;
					if(openPoint!=null){
						//如果从当前路径的G值大于了原始G值，舍弃
						if(AStartUtils.countGvalue(currentPoint,openPoint)+currentPoint.gValueTotal >= openPoint.gValueTotal){
							continue ;
						}else{
							//设置此点的父节点为当前点
							openPoint.parentPoint = currentPoint ;
							openPoint.hValue = AStartUtils.countHValue(openPoint,endPoint);
							openList.addItem(openPoint);
							continue;
						}
					}
					//如果是新节点，加入到开启列表
					temp.parentPoint = currentPoint ;
					temp.hValue = AStartUtils.countHValue(temp,endPoint);
					openList.push(temp);
					grid[y][x] = OPEN ;
				}
			}
		}
		
		/*计算图形上的列数即X最大值*/
		private function getMaxCol(grid:Array):int{
			if(grid.length>0 && grid[0]!=null){
				return (grid[0] as Array).length ;
			}
			return 0 ;
		}
		
		/*检查某点是否在列表开启列表中*/
		private function checkPointInList(p:APoint,grid:Array):APoint{
			var t:uint = new Date().time;
			if(grid[p.y][p.x]==OPEN){
				var t1:uint = new Date().time ;
				tn2 += (t1-t);
				return p ;
			}
			return null ;
		}
		
	}
}